//
//  ProbelmOffer66.swift
//  TestProject
//
//  Created by 武侠 on 2021/7/19.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 66. 构建乘积数组 ✅
 给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

 示例:
     输入: [1,2,3,4,5]
     输出: [120,60,40,30,24]
 提示：
     所有元素乘积之和不会溢出 32 位整数
     a.length <= 100000
 */
@objcMembers class ProbelmOffer66: NSObject {
    func solution() {
        print(constructArrY([1,2,3,4,5]))
        print(constructArrY([1,2]))
        print(constructArrY([1,2,3]))
    }
    
    /*
     前缀积 + 后缀积
     */
    func constructArr(_ a: [Int]) -> [Int] {
        if a.count <= 1 {
            return a
        }
        
        var pList  = a, nList  = a, result = a
        
        // 前缀积
        for i in 1...a.count-1 {
            pList[i] *= pList[i-1]
        }
        
        // 后缀积
        for i in (0...a.count-2).reversed() {
            nList[i] *= nList[i+1]
        }
        
        result[0] = nList[1]
        result[a.count-1] = pList[a.count-2]
        if a.count > 2 {
            for i in 1...a.count-2 {
                result[i] = pList[i-1] * nList[i+1]
            }
        }
        
        return result
    }
    
    /*
     前缀积 + 后缀积
     优化空间
     */
    func constructArrY(_ a: [Int]) -> [Int] {
        if a.count <= 1 {
            return a
        }
        
        var result = a
        // 前缀积
        for i in 1...a.count-1 {
            result[i] *= result[i-1]
        }
        
        result[a.count-1] = result[a.count-2]
        // 后缀积
        var last = 1
        if a.count > 2 {
            for i in (1...a.count-2).reversed() {
                last *= a[i+1]
                result[i] = result[i-1] * last
            }
        }
        
        result[0] = last * a[1]
        return result
    }
        
}
